#include <bits/stdc++.h>
using namespace std;
const int N=205;
int g[N][N];
int n,m,k;
void floyd()
{
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
			}
			
		}
	}
}
int main()

{
	cin>>n>>m>>k;
	while(m--)
	{
		int a,b,c;
		cin>>a>>b>>c;
		g[a][b]=min(g[a][b],c);
	}
	floyd();
	while(k--)
	{
		int a,b;
		cin>>a>>b;
		int t=g[a][b];
		if(t>0x3f3f3f3f/2) printf("impossible\n");
		else printf("%d\n",t);
	}
}
